package cn.edu.jxau.test;

import java.io.IOException;

import cn.edu.jxau.util.LinkedQueue;

public class Main {

    public static void main(String[] args) throws IOException {

        LinkedQueue<Integer> queue1 = new LinkedQueue<>();
        queue1.enqueue(23);
        LinkedQueue<Integer> queue2 = new LinkedQueue<>();
        queue2.enqueue(53);
        LinkedQueue<Integer> queue3 = new LinkedQueue<>();
        queue3.enqueue(89);
        LinkedQueue<Integer> queue4 = new LinkedQueue<>();
        queue4.enqueue(12);
        LinkedQueue<Integer> queue5 = new LinkedQueue<>();
        queue5.enqueue(56);
        LinkedQueue<Integer> queue6 = new LinkedQueue<>();
        queue6.enqueue(34);
        LinkedQueue<Integer> queue7 = new LinkedQueue<>();
        queue7.enqueue(90);
        LinkedQueue<Integer> queue8 = new LinkedQueue<>();
        queue8.enqueue(23);
        LinkedQueue<Integer> queue9 = new LinkedQueue<>();
        queue9.enqueue(12);
        LinkedQueue<LinkedQueue<Integer>> queue = new LinkedQueue<>();
        queue.enqueue(queue1);
        queue.enqueue(queue2);
        queue.enqueue(queue3);
        queue.enqueue(queue4);
        queue.enqueue(queue5);
        queue.enqueue(queue6);
        queue.enqueue(queue7);
        queue.enqueue(queue8);
        queue.enqueue(queue9);
        System.out.println(sort(queue));
    }

    /**
     * 队列的队列，{@code queue}中的元素是一个仅包含一个元素的队列
     * @param queue
     * @return
     */
    private static LinkedQueue<Integer> sort(LinkedQueue<LinkedQueue<Integer>> queue) {

        while (queue.size() > 1) {
            LinkedQueue<Integer> mergeQueue = merge(queue.dequeue(), queue.dequeue());
            queue.enqueue(mergeQueue);
        }
        return queue.dequeue();
    }

    private static LinkedQueue<Integer> merge(LinkedQueue<Integer> queue1, LinkedQueue<Integer> queue2) {

        LinkedQueue<Integer> result = new LinkedQueue<Integer>();
        while (!queue1.isEmpty() && !queue2.isEmpty()) {
            if (queue1.look() < queue2.look()) {
                result.enqueue(queue1.dequeue());
            } else {
                result.enqueue(queue2.dequeue());
            }
        }
        while (!queue1.isEmpty()) {
            result.enqueue(queue1.dequeue());
        }
        while (!queue2.isEmpty()) {
            result.enqueue(queue2.dequeue());
        }
        return result;
    }

}
